package leetcode104

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var left int
	var right int
	left = maxDepth(root.Left)
	right = maxDepth(root.Right)
	if left > right {
		return left + 1
	} else {
		return right + 1
	}
}

func maxDe(left, right *TreeNode, depth int) int {
	if left == nil && right == nil {
		return depth
	} else if left == nil {
		return maxDe(right.Left, right.Right, depth+1)
	} else if right == nil {
		return maxDe(left.Left, left.Right, depth+1)
	} else {
		leftDe := maxDe(left.Left, left.Right, depth+1)
		rightDe := maxDe(right.Left, right.Right, depth+1)
		if leftDe > rightDe {
			return leftDe
		} else {
			return rightDe
		}
	}
}
